package com.aqie.easy.structure;

public class AVLTree2 {
    public NewNode root;
    /**
     * 计算AVL节点的高度的方法
     */
    private int height(NewNode NewNode) {
        //如果为空，返回height为0
        return NewNode == null ? 0 : NewNode.height;
    }
    /**
     * 计算两个的最大值
     */
    private int max(int a, int b) {
        return a > b ? a : b;
    }
    /**
     * 右旋转
     */
    NewNode rightRotate(NewNode y) {
        NewNode x = y.left;
        NewNode T1 = x.right;
        x.right = y;
        y.left = T1;
        //更新高度
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;
        return x;
    }

    /**
     * 左旋转
     */
    NewNode leftRotate(NewNode x) {

        NewNode y = x.right;
        NewNode T2 = y.left;
        y.left = x;
        x.right = T2;
        //更新高度
        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;
        return y;
    }
    /**
     *  获取平衡因子
     */
    int getBalance(NewNode NewNode) {
        return NewNode == null ? 0 : (height(NewNode.left) - height(NewNode.right));
    }

    /**
     * 插入操作
     */
    public NewNode insert(NewNode NewNode,int key, int val) {
        if (NewNode == null) {
            return new NewNode(key,val);
        }
        if (key < NewNode.key) {
            NewNode.left = insert(NewNode.left, key,val);
        } else if (key > NewNode.key) {
            NewNode.right = insert(NewNode.right, key,val);
        } else {
            NewNode.val = val;
            return NewNode;
        }
        //更新节点高度
        NewNode.height = 1 + max(height(NewNode.left), height(NewNode.right));
        //这是插入完毕后的
        int balance = getBalance(NewNode);
        if (balance > 1 && key < NewNode.left.key) {
            //右旋
            return rightRotate(NewNode);
        }
        if (balance < -1 && key > NewNode.right.key) {
            //左旋
            return leftRotate(NewNode);
        }
        if (balance > 1 && key > NewNode.left.key) {
            //先左旋，再右旋
            NewNode.left = leftRotate(NewNode.left);
            return rightRotate(NewNode);
        }
        if (balance < -1 && key < NewNode.right.key) {
            //先右旋再左旋
            NewNode.right = rightRotate(NewNode.right);
            return leftRotate(NewNode);
        }
        return NewNode;
    }

    /**
     * 获取值
     */
    public NewNode getAVLTree(int key,NewNode node){
        if(node==null) return null;
        if(key>node.key){
            node = getAVLTree(key,node.right);
        }else if(key<node.key){
            node = getAVLTree(key,node.left);
        }
        if(node!=null&&key==node.key) return node;
        else return null;
    }

    /**
     * 删除值
     */
    public NewNode deleteNode(NewNode root, int key) {
        if (root == null) {
            return root;
        }
        if (key < root.key) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.key) {
            root.right = deleteNode(root.right, key);
        } else {
            //删除节点有两个孩子
            if (root.left != null && root.right != null) {
                root.val = findMin(root.right).val;
                root.key = findMin(root.right).key;
                root.right = deleteNode(root.right, root.key);
            } else {
                //删除节点只有一个孩子或者没有孩子
                root = (root.left != null) ? root.left : root.right;
            }
        }
        //以下操作是为了恢复AVL树的平衡性
        if (root == null) {
            return root;
        }
        root.height = max(height(root.left), height(root.right)) + 1;
        int balance = getBalance(root);
        //左-左情况，这里使用>=而不是>就是为了保证这些情形下使用的是单旋转而不是双旋转
        if (balance > 1 && getBalance(root.left) >= 0) {
            return rightRotate(root);
        }

        //左-右情况
        if (balance > 1 && getBalance(root.left) < 0)
        {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        //右-右情况
        if (balance < -1 && getBalance(root.right) <= 0) {
            return leftRotate(root);
        }
        //右-左情况
        if (balance < -1 && getBalance(root.right) > 0)
        {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }
        return root;
    }

    private NewNode findMin(NewNode root) {
        if (root.left == null) {
            return root;
        } else {
            return findMin(root.left);
        }
    }

}
